package Offer6;

import java.util.Stack;

/**
 * 从尾到头打印链表
 * @author 23737
 * @time 2021.10.14
 */
public class Test {
    public static void main(String[] args) {

    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

//暴力题解
class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode temp = head;
        while(temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        int[] reverse = new int[stack.size()];
        for (int i = 0; i < reverse.length; i++) {
            reverse[i] = stack.pop().val;
        }
        return  reverse;
    }
}

//双一百解法
class Solution2 {
    // 执行用时 : 0 ms, 在所有 Java 提交中击败了 100.00% 的用户
    // 内存消耗 : 39.8 MB, 在所有 Java 提交中击败了 100.00% 的用户
    // 我就不使用栈，就不使用递归，反正怎么样也是扫描两趟，为什么要额外分配空间呢？
    // 感谢 @谢飞机 的灵感。
    public static int[] reversePrint(ListNode head) {
        ListNode node = head;
        int count = 0;
        while (node != null) {
            ++count;
            node = node.next;
        }
        int[] nums = new int[count];
        node = head;
        //这里运用到的思想值得学习，通过从数组的尾部来进行赋值，然后再将数组正序返回
        for (int i = count - 1; i >= 0; --i) {
            nums[i] = node.val;
            node = node.next;
        }
        return nums;
    }
}
